/*
 * Путь в ациклическом графе
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))

struct edge {
	int x, y, weight;
};

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* doubly-linked list */
struct dll_node {
	int x, y;
	int z;
	char *data;
	size_t _data_size;
	struct dll_node *prev, *next;
};

/* graph repr: adjlist w/ doubly-linked list */
enum vertex_st {
	VTX_ST_UNKN = 0,
	VTX_ST_ENQUEUED,
	VTX_ST_OPEN,
	VTX_ST_VISITED
};

struct adjlist_dll {
	struct dll_node *head;
	struct dll_node *tail;
	size_t _list_len;

	enum vertex_st state;
	/*int color;*/
	int dist;
	int parent;
	/*int fwd, bck;*/ /* dfs tree depth, >=1 unless uninitialized */
	/*int low;*/ /* lowpoint(), >=1 unless uninitialized */
	/*int chnum;*/ /* children count for this node */
};

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0 || p >= (int) (CHAR_BIT * sizeof v->data[0]))
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		fprintf(stderr, "%s(): v->_max is 0, which means that your "
				"autoarray (v=%p) is messed up. trying to fix this.\n",
				__func__, (void*) v);
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern void *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

/* {{{ doubly-linked list */
/*
 * This function inserts one node pointed to by 'ins' _after_ 'node'.
 */
extern struct dll_node *
dll_insert(struct dll_node *node, struct dll_node *ins)
{
	assert(node != NULL);
	if (ins == NULL) {
		debug_fprintf((stderr, "dll_insert(): ins is NULL, not doing anything\n"));
		return node;
	}

	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = ins;
	}
	ins->next = node->next;
	ins->prev = node;
	node->next = ins;
	return ins;
}

/*
 * This function extracts 'node' from a doubly-linked list and returns pointer
 * to that node, pointers '->prev' and '->next' are not reset.
 *
 * If you really want to get rid of a node, call
 * 	free(dll_delete(unneeded_node));
 */
extern struct dll_node *
dll_delete(struct dll_node *node)
{
	if (!node) {
		debug_fprintf((stderr, "dll_delete(): received NULL ptr, wtf am i supposed to delete?\n"));
		return NULL;
	}

	if (node->prev) {
		assert(node->prev->next == node);
		node->prev->next = node->next;
	}
	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = node->prev;
	}

	return node;
}

/*
 * Merge-sort for doubly-linked list.
 *
 * TODO: work out the use of (*cmp)() function
 */
extern void
dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *))
{
	struct dll_node *end, *mid;
	struct dll_node *sorted, *first, *second;
	struct dll_node *swap;

	if (head == NULL || head->next == NULL) /* lengths 0, 1 */
		return;

	end = mid = head;
	while (end && end->next && end->next->next) {
		end = end->next->next;
		mid = mid->next;
	}
	if (end && end->next) {
		end = end->next;
		mid = mid->next;
	}

	mid->prev->next = NULL;
	mid->prev = NULL;
	dll_mergesort(head, cmp);
	dll_mergesort(mid, cmp);

	if (cmp(head->data, mid->data) > 0) { /* this is the tricky part */
		char *t1;
		size_t t2;
		struct dll_node *t3;
		int t4;
#define SWAP_(a,b,t) do{(t)=(a),(a)=(b),(b)=(t);}while(0)
		if (head->next && mid->next)
			SWAP_(head->next->prev, mid->next->prev, t3);
		SWAP_(head->x, mid->x, t4);
		SWAP_(head->data, mid->data, t1);
		SWAP_(head->_data_size, mid->_data_size, t2);
		SWAP_(head->prev, mid->prev, t3);
		SWAP_(head->next, mid->next, t3);
#undef SWAP_
	}

	/*
	 * from now on using only ->prev and ->next pointers should suffice us
	 */
	first = head->next;
	if (first) first->prev = NULL;
	second = mid;

	sorted = head;
	sorted->next = NULL;
	assert(sorted->prev == NULL);

	while (first && second) {
		assert(sorted->next == NULL);

		/* TODO: un-copypaste this code (use 'swap' ptr) */
		if (cmp(first->data, second->data) < 0)
			swap = first;
		else
			swap = second;

		assert(swap->prev == NULL);

		sorted->next = swap;
		swap->prev = sorted;
		sorted = swap;

		swap = swap->next;
		if (swap) {
			assert(swap->prev == sorted);
			swap->prev->next = NULL;
			swap->prev = NULL;
		}
	}
	assert(sorted->next == NULL);
	if (first) {
		assert(first->prev == NULL);
		sorted->next = first;
		first->prev = sorted;
	}
	if (second) {
		assert(second->prev == NULL);
		sorted->next = second;
		second->prev = sorted;
	}
}
/* }}} */

/* {{{ graph repr: adjlist w/ doubly-linked list */
extern void
adjl_dll_connect(struct adjlist_dll *node, const int conid, const int edgeid, const int z)
{
	struct dll_node *Wilson;

	Wilson = (struct dll_node *) s_calloc(1, sizeof *Wilson);
	Wilson->x = conid;
	Wilson->y = edgeid;
	Wilson->z = z;
	Wilson->prev = Wilson->next = NULL;

	if (node->head == NULL) {
		assert(node->tail == NULL);
		node->head = node->tail = Wilson;
		node->_list_len = 1;
	} else {
		node->tail = dll_insert(node->tail, Wilson);
		node->_list_len++;
	}
}

extern void
adjl_dll_cleanup(struct adjlist_dll *al)
{
	struct dll_node *nx = al->head, *pr = al->head;

	while (nx) {
		pr = nx;
		nx = nx->next;
		free(pr);
	}
	al->_list_len = 0;
	al->head = al->tail = NULL;
}
/* }}} */

int
dfs_toposort(struct adjlist_dll *al, struct vector *order, const int s)
{
	struct dll_node *nd = NULL;

	assert(al != NULL);
	assert(order != NULL);

	debug_fprintf((stderr, "%s(): entered node %d\n", __func__, s + 1));

	al[s].state = VTX_ST_OPEN;
	nd = al[s].head;
	while (nd) {
		debug_fprintf((stderr, "%s(): looking at edge (%d, %d) weight %d\n",
					__func__, s + 1, nd->x + 1, nd->y + 1));
		if (al[nd->x].state == VTX_ST_OPEN)
			debug_fprintf((stderr, "found cycle on edge (%d, %d)\n",
						s + 1, nd->x + 1));
		if (al[nd->x].state == VTX_ST_UNKN)
			dfs_toposort(al, order, nd->x);
		nd = nd->next;
	}
	al[s].state = VTX_ST_VISITED;
	vector__append(order, &s);

	debug_fprintf((stderr, "%s(): leaving node %d, adding it to 'order'\n",
				__func__, s + 1));

	return 0; /* XXX */
}

int
bellman_ford(struct adjlist_dll *al, struct vector *order,
		struct vector *E, const int N)
{
	struct dll_node *nd;
	struct edge *e;
	int *ord;
	int i;
	register int r;

	assert(al != NULL);
	assert(E != NULL);

	e = E->data;
	ord = order->data;

	/* update vertex distances */
	// for (r = 0; r < N; r++)
	//     al[r].dist = INT_MAX;
	// al[0].dist = 0;

	/* s1 */
	for (i = order->n - 1; i >= 0; i--) {
		for (nd = al[ord[i]].head; NULL != nd; nd = nd->next)
		{
			r = nd->z;

			debug_fprintf((stderr, "%s(): stage1: "
					"edge (%d, %d) w=%d\n",
					__func__, ord[i] + 1, nd->x + 1, nd->y));

			S_assert(e[r].x == ord[i]);
			S_assert(e[r].y == nd->x);
			S_assert(e[r].weight == nd->y);

			if (al[e[r].x].dist < INT_MAX &&
				al[e[r].y].dist > al[e[r].x].dist + e[r].weight) {
				debug_fprintf((stderr, "bellman_ford(stage1:%6$d): "
					"edge (%1$d, %2$d) %3$d: d[%1$d]=%4$d > d[%2$d]=%5$d + weight=%3$d\n",
					e[r].y + 1, e[r].x + 1, e[r].weight, al[e[r].y].dist,
					al[e[r].x].dist, i));
				al[e[r].y].dist = al[e[r].x].dist + e[r].weight;
				al[e[r].y].parent = e[r].x;
			}
		}
	}

	/* s2 */
	for (i = order->n - 1; i >= 0; i--) {
		for (nd = al[ord[i]].head; NULL != nd; nd = nd->next)
		{
			r = nd->z;

			debug_fprintf((stderr, "%s(): stage2: "
					"edge (%d, %d) w=%d\n",
					__func__, ord[i] + 1, nd->x + 1, nd->y));

			if (al[e[r].x].dist < INT_MAX &&
				al[e[r].y].dist > al[e[r].x].dist + e[r].weight ||
				al[e[r].x].dist == INT_MIN) {
				debug_fprintf((stderr, "bellman_ford(stage2:%6$d): "
					"edge (%1$d, %2$d) %3$d: d[%1$d]=%4$d > d[%2$d]=%5$d + weight=%3$d\n",
					e[r].y + 1, e[r].x + 1, e[r].weight, al[e[r].y].dist,
					al[e[r].x].dist, i));
				al[e[r].y].dist = INT_MIN;
				al[e[r].y].parent = e[r].x;
			}
		}
	}

	return 0;
}

void
print_path_rec(const struct adjlist_dll *al, const int s, const int f)
{
	if (f != -1)
	{
		print_path_rec(al, s, al[f].parent);
		printf("%d ", f + 1);
	}
}

int
print_path(const struct adjlist_dll *al, const int s, const int f)
{
	int len = 0, i;

	i = f;
	while (i != -1)
	{
		len++;
		i = al[i].parent;
	}
	printf("%d\n", len);
	print_path_rec(al, s, f);
	fputc('\n', stdout);

	return 0;
}

int
main(int argc, char **argv)
{
	struct vector *E = NULL;
	struct adjlist_dll *al = NULL;
	struct vector *ord = NULL;
	int n, m, start, finish,
		i, a, b, w;
	struct edge x;

	ord = vector__new(sizeof (int), 4);
	E = vector__new(sizeof (struct edge), 4);

	scanf("%d %d %d %d", &n, &m, &start, &finish);
	--start; --finish;
	al = s_calloc(n, sizeof *al);

	for (i = 0; i < n; i++) {
		al[i].parent = -1;
		al[i].dist = INT_MAX;
	}
	al[start].dist = 0;

	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &w);
		--a; --b;
		adjl_dll_connect(al + a, b, w, i);

		x.x = a;
		x.y = b;
		x.weight = w;
		vector__append(E, &x);
	}

	dfs_toposort(al, ord, start);
	if (al[finish].state == VTX_ST_VISITED)
	{
		bellman_ford(al, ord, E, n);
		print_path(al, start, finish);
	}
	else
	{
		puts("-1");
	}

	for (i = 0; i < n; i++)
		adjl_dll_cleanup(al + i);
	free(al);
	vector__cleanup(E);
	vector__cleanup(ord);
	return 0;
}
